//这次要求求出所有路径总数为某数的路径并打印
#include <vector>
#include <queue>
#include <stack>
#include <utility>
using std::pair;
using std::stack;
using std::queue;
using std::vector;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};


//递归法
//同样对于path和count，都需要进行回溯操作，撤销修改结果
vector<int> path;
vector<vector<int>> result;
void traversal(TreeNode* cur,int count)
{
    if(!cur->left&&!cur->right&&count==0){
        result.push_back(path);
        return ;
    }
    if(!cur->left&&!cur->right) return ;

    if(cur->left){
        path.push_back(cur->left->val);
        count-=cur->left->val;
        traversal(cur->left,count);
        //回溯撤销
        path.pop_back();
        count+=cur->left->val;
    }

    if(cur->right){
        path.push_back(cur->right->val);
        count-=cur->right->val;
        traversal(cur->right,count);
        //撤销
        path.pop_back();
        count+=cur->right->val;
    }
}

vector<vector<int>> pathSum_recursion(TreeNode* root,int targetSum){
    if(!root) return result;
    path.push_back(root->val);
    targetSum-=root->val;

    traversal(root,targetSum);
    return result;
}




//迭代法，使用栈和回溯算法实现
/*
要注意的几个点：
1.path和node.second()即路径总数一定要同时更新，保证两两对应
2.左右子树处理完path后要回溯，即撤销处理结果，否则左子树用的就是错误的path
*/
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        stack<vector<int>> pathst;//存放当前节点对应路径
        stack<pair<TreeNode*, int>> st;

        if (!root)
            return result;
        st.push(pair<TreeNode*, int>(root, root->val));
        pathst.push({root->val});
        //栈的深度前序遍历实现
        while (!st.empty()) {
            //栈同时弹出，同时压入，保证节点和路径和路径总数是对应的
            pair<TreeNode*, int> node = st.top();
            st.pop();
            vector<int> path = pathst.top();
            pathst.pop();

            if (!node.first->left && !node.first->right &&
                node.second == targetSum) {
                result.push_back(path);
            }

            if (node.first->right) {
                path.push_back(node.first->right->val);
                st.push(pair<TreeNode*, int>(
                    node.first->right, node.second + node.first->right->val));
                pathst.push(path);
                //最重要的一点：这里一定要回溯，否则下面左子树用的就是不对的path！！！
                path.pop_back();
            }

            if (node.first->left) {
                path.push_back(node.first->left->val);
                st.push(pair<TreeNode*, int>(
                    node.first->left, node.second + node.first->left->val));
                pathst.push(path);
                //回溯，虽然这里没什么意义但还是写上要更清晰一点
                path.pop_back();
            }
        }

        return result;
    }




//使用队列的算法，并用一个结构体来存储path和路径总数
struct point {
        vector<int> path;
        int curSum;
        point(vector<int> _path, int _curSum) :path(_path), curSum(_curSum) {}
    };


    using ptp = pair<TreeNode*, point>;
    vector<vector<int>> ans;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (!root) {
        return ans;
        }
        queue<ptp>q;
        point p(vector<int>(), 0);
        q.emplace(root, p);
        while (!q.empty()) {
            auto [node, pt] = q.front();       //node得到TreeNode*部分，pt得到point部分
            // cout << node->val << endl;
            q.pop();
            pt.curSum += node->val;
            pt.path.emplace_back(node->val);
            if (!node->left && !node->right) {
                if (pt.curSum == targetSum) {
                ans.emplace_back(pt.path);
                }
            }
            if (node->left) {
                q.emplace(node->left, pt);
            }
            if (node->right) {
                q.emplace(node->right, pt);
            }
        }
        return ans;
    }